A searchable encryption system enables a search user to search for data stored in a server by specifying a keyword, and at that time the data and the keyword are kept secret to the server.
Searchable encryption systems are expected to be applied to outsourcing of confidential data management and filtering of encrypted mail messages in a mail server.
Thus, as techniques for searchable encryption systems, there have been proposed techniques for achieving various security requirements and techniques for reducing storage, communication overhead, and computational overhead of servers and search users.
In particular, in a searchable encryption technique based on deterministic encryption, the same keyword corresponds to the same encrypted keyword, so that a server is only required to search for matching data based on a specified encrypted keyword. This allows acceleration using existing search techniques.
However, when a keyword is encrypted using deterministic encryption, the frequency information of the keyword is directly reflected in the frequency information of the encrypted keyword. Therefore, by investigating the frequency of an encrypted keyword, a corresponding keyword can be guessed. That is, an attack called “frequency analysis” is possible.
As a countermeasure against this frequency analysis, there is a method in which dummy data is inserted to disturb frequencies.
Patent Literature 1 discloses a method for generating dummy data using character strings not normally used in searching, such as punctuation marks. By this method, resistance against frequency analysis can be provided without increasing the database size.